package com.xiayuanxing.arithmetic.DataStructures.Sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: arithmetic
 * @description: 基数排序
 * @author: xia yuan xing
 * @create: 2021-09-27 09:44
 */
public class BasicSort {

    public static void main(String[] args) {
        int[] array = {8,4,5,7,1,3,6,2};

//        basicSort(array);
//        System.out.println(Arrays.toString(array));
//        radixSort(array);
        radixOverSort(array);
    }


   /**
   *@Description: 基数排序：方法一
   *@Param: 要排序的数组（原始数组）
   *@return:
   *@Author: xia yuan xing
   *@date: 2021/9/27
   */
    public static void basicSort(int[] array){
        int max = 0;
        for (int i = 0; i <array.length ; i++) {
            if (array[i] > max){
                max = array[i];
            }
        }

        int times = 0;
        while (max > 0){
            max = max/10;
            times ++;
        }

        List<ArrayList> queen = new ArrayList<ArrayList>();
        for (int i = 0; i < 10 ; i++) {
            ArrayList q = new ArrayList();
            queen.add(q);
        }

        for (int i = 0; i < times ; i++) {
            for (int j = 0; j < array.length ; j++) {
                int x = array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
                ArrayList q = queen.get(x);
                q.add(array[j]);
            }

            int count = 0;
            for (int z = 0; z < 10 ; z++) {
                while (queen.get(z).size()>0){
                    ArrayList<Integer> c = queen.get(z);
                    array[count] = c.get(0);
                    c.remove(0);
                    count++;
                }
            }
        }
    }



    /**
    *@Description: 基数排序：方法二(推导式)
    *@Param: 要排序的数组（原始数组）
    *@return:
    *@Author: xia yuan xing
    *@date: 2021/9/27
    */
    public static void radixSort(int[] arr){


        //定义一个二维数组表示十个桶，每个桶就是一个一维数组
        //说明：1.二维数组包含10个一维数组
        //2.为了防止在放入数的时候，数据溢出，则每个一维数组大小定为arr.length
        //3.基数排序是用空间换时间
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以理解为：bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数
        int[] bucketElementCounts = new int[10];

        //第一轮排序：针对每个元素的个位进行排序处理
        for (int j = 0; j < arr.length ; j++) {
            //取出每个元素的个位的值
            int digitOfElement = arr[j] % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        //按照这个桶的顺序（一维数组的下标依次取出数据，放入到原来的数组中）
        int index = 0;
        //遍历每一个桶，并将桶中的每一个数据放入数组
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶内有数据，才放入原数组
            if (bucketElementCounts[k] != 0){
                //循环该桶即第k个桶（即第k个一维数组），放入
                for (int l = 0; l < bucketElementCounts[k] ; l++) {
                    //取出元素放入到arr中
                    arr[index++] = bucket[k][l];
                }
            }
            //处理完第一轮后将bucketElementCounts[k]置为0
            bucketElementCounts[k] = 0;
        }
        System.out.println("第一轮："+Arrays.toString(arr));



        //第二轮排序：针对每个元素的十位进行排序处理
        for (int j = 0; j < arr.length ; j++) {
            //取出每个元素的个位的值
            int digitOfElement = arr[j]/10 % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        //按照这个桶的顺序（一维数组的下标依次取出数据，放入到原来的数组中）
        index = 0;
        //遍历每一个桶，并将桶中的每一个数据放入数组
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶内有数据，才放入原数组
            if (bucketElementCounts[k] != 0){
                //循环该桶即第k个桶（即第k个一维数组），放入
                for (int l = 0; l < bucketElementCounts[k] ; l++) {
                    //取出元素放入到arr中
                    arr[index++] = bucket[k][l];
                }
            }
            //处理完第一轮后将bucketElementCounts[k]置为0
            bucketElementCounts[k] = 0;
        }
        System.out.println("第二轮："+Arrays.toString(arr));


        //第三轮排序：针对每个元素的百位进行排序处理
        for (int j = 0; j < arr.length ; j++) {
            //取出每个元素的个位的值
            int digitOfElement = arr[j]/100 % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        //按照这个桶的顺序（一维数组的下标依次取出数据，放入到原来的数组中）
        index = 0;
        //遍历每一个桶，并将桶中的每一个数据放入数组
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶内有数据，才放入原数组
            if (bucketElementCounts[k] != 0){
                //循环该桶即第k个桶（即第k个一维数组），放入
                for (int l = 0; l < bucketElementCounts[k] ; l++) {
                    //取出元素放入到arr中
                    arr[index++] = bucket[k][l];
                }
            }
            //处理完第一轮后将bucketElementCounts[k]置为0
            bucketElementCounts[k] = 0;
        }
        System.out.println("第三轮："+Arrays.toString(arr));
    }


    /**
     *@Description: 基数排序：方法三(推导式最终整合)
     *@Param: 要排序的数组（原始数组）
     *@return:
     *@Author: xia yuan xing
     *@date: 2021/9/27
     */
    public static void radixOverSort(int[] arr){

        //1.得到数组中最大的数的位数
        int max = arr[0];//假设第一数就是最大数
        for (int i = 1; i < arr.length ; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();

        //定义一个二维数组表示十个桶，每个桶就是一个一维数组
        //说明：1.二维数组包含10个一维数组
        //2.为了防止在放入数的时候，数据溢出，则每个一维数组大小定为arr.length
        //3.基数排序是用空间换时间
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以理解为：bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数
        int[] bucketElementCounts = new int[10];

        for (int i = 0,n = 1; i < maxLength ; i++,n *= 10) {

            //第i轮排序：针对每个元素的个/十/百位进行排序处理
            for (int j = 0; j < arr.length ; j++) {
                //取出每个元素的个位的值
                int digitOfElement = arr[j]/n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }

            //按照这个桶的顺序（一维数组的下标依次取出数据，放入到原来的数组中）
            int index = 0;
            //遍历每一个桶，并将桶中的每一个数据放入数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶内有数据，才放入原数组
                if (bucketElementCounts[k] != 0){
                    //循环该桶即第k个桶（即第k个一维数组），放入
                    for (int l = 0; l < bucketElementCounts[k] ; l++) {
                        //取出元素放入到arr中
                        arr[index++] = bucket[k][l];
                    }
                }
                //处理完第i+1轮后将bucketElementCounts[k]置为0
                bucketElementCounts[k] = 0;
            }
            System.out.println("第"+i+"轮："+Arrays.toString(arr));
        }
    }
}